#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
class maxstack
{
private:
	int mystack[100];
	int top;
	int link2nextMax[100];
	int curmaxindex;
public:
	maxstack()
	{
		top=-1;
		curmaxindex=-1;
	}
	void push(int x)
	{
		top++;
		mystack[top]=x;
		if(x>max())
		{
			link2nextMax[top]=curmaxindex;
			curmaxindex=top;
		}
		else 
			link2nextMax[top]=-1;
	}
	int pop()
	{
		if(top>=0)
		{
			int popout=mystack[top];

			if(popout==mystack[curmaxindex])
			{
				curmaxindex=link2nextMax[top];
			}
			top--;			
			return popout;
		}
	}
	int max()
	{
		if(curmaxindex>=0) return  mystack[curmaxindex];
		else return -5622;
	}
	bool empty()
	{
		return top==-1;
	}
};

class maxque
{
private:
	maxstack s1;
	maxstack s2;
public:
	void enque(int x)
	{
		s1.push(x);	
	}
	int deque()
	{
		if(s2.empty())
		{
			while(!s1.empty())
			{
				s2.push(s1.pop());
			}
		}
		return s2.pop();
	}
	int max()
	{
		return maxvalue(s1.max(),s2.max());
	}
	int maxvalue(int x,int y)
	{
		return x>y?x:y;
	}
};
int main()
{
	maxstack mxt;
	mxt.push(1);
	mxt.push(4);
	mxt.push(2);
	mxt.push(8);
	for(int i=0;i<4;i++)
	{
		cout<<mxt.pop();
		cout<<"max:"<<mxt.max();
		cout<<endl;
	}

	maxque mxq;
	mxq.enque(8);
	mxq.enque(4);
	mxq.enque(2);
	mxq.enque(1);
	for(int i=0;i<4;i++)
	{
		cout<<mxq.deque();
		cout<<"max:"<<mxq.max();
		cout<<endl;
	}
	system("pause");
	return 0;
}